/**
 * @file kmp.cpp
 * @brief KMP算法
 * @author Xavier ZXY (zxy_xavier@163.com)
 * @version : 1.0
 * @date 2022-05-15
 *
 */
#include <string.h>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

using namespace std;

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */

typedef int Status;   /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */

typedef char String[MAXSIZE + 1]; /*  0号单元存放串的长度 */

Status StrAssign(String T, char *chars);    // 生成一个值等于chars的串
Status ClearString(String S);               //令串长为0
void StrPrint(String T);                    //输出字符串
void NextPrint(int next[], int length);     //输出Next数组值
int StrLength(String S);                    //返回元素的个数
int Index(String S, String T, int pos);     //朴素的模式匹配法
void get_next(String T, int *next);         //通过计算返回子串的next数组
int Index_KMP(String S, String T, int pos); //
void get_nextval(String T, int *nextval);   //求模式串的next函数修正值
int Index_KMP1(String S, String T, int pos);

int main(int argc, char const *argv[])
{
    int i, *p;
	String s1, s2;

	StrAssign(s1, "000200000000020000000002000000000200000000020000000001");
	printf("主串为: ");
	StrPrint(s1);
	StrAssign(s2, "0000001");
	printf("子串为: ");
	StrPrint(s2);
	printf("\n");

	printf("\n");
	printf("开始匹配");
	printf("主串和子串在第%d个字符处首次匹配（朴素模式匹配算法）\n", Index(s1, s2, 1));
	printf("主串和子串在第%d个字符处首次匹配（KMP算法） \n", Index_KMP(s1, s2, 1));
	printf("主串和子串在第%d个字符处首次匹配（KMP改良算法） \n", Index_KMP1(s1, s2, 1));

	return 0;
}

Status StrAssign(String T, char *chars)
{
    int i;
    if (strlen(chars) > MAXSIZE)
        return ERROR;
    else
    {
        T[0] = strlen(chars);
        for (i = 1; i <= T[0]; i++)
            T[i] = *(chars + i - 1);
    }

    return OK;
}

Status ClearString(String S)
{
    S[0] = 0;

    return OK;
}

void StrPrint(String T)
{
    for (int i = 0; i <= T[0]; i++)
        printf("%c", T[i]);
    printf("\n");
}

void NextPrint(int next[], int length)
{
    for (int i = 0; i <= length; i++)
        printf("%d", next[i]);
    printf("\n");
}

int StrLength(String S)
{
    return S[0];
}

/**
 * @brief 朴素匹配
 * @return int
 */
int Index(String S, String T, int pos)
{
    int n = 0;
    int i = pos;                   /* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
    int j = 1;                     /* j用于子串T中当前位置下标值 */
    while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
    {
        if (S[i] == T[j]) /* 两字母相等则继续 */
        {
            ++i;
            ++j;
        }
        else /* 指针后退重新开始匹配 */
        {
            i = i - j + 2; /* i退回到上次匹配首位的下一位 */
            j = 1;         /* j退回到子串T的首位 */
        }

    }
    if (j > T[0])
        return i - T[0];
    else
        return 0;
}

/**
 * @brief Get the next object of T
 */
void get_next(String T, int *next)
{
    int j = 0;
    next[1] = 0;
    for (int i = 2; i <= T[0]; i++)
    {
        while (j > 0 && T[i] != T[j + 1])
        {                //前后缀不相同
            j = next[j]; //向前回退
        }

        if (T[i] == T[j + 1])
            j++;
        next[i] = j;
    }
}

/**
 * @brief KMP算法
 */
int Index_KMP(String S, String T, int pos)
{
    int next[T[0]];
    get_next(T, next);

    int j = 0; //前缀指针
    for (int i = pos; i <= S[0]; i++)
    {
        while (j > 0 && S[i] != T[j + 1])
        {
            j = next[j];
        }

        if (S[i] == T[j + 1])
        {
            j++;
        }

        if (j == T[0])
            return i - T[0] + 1;
    }

    return 0;
}

/**
 * @brief Get the nextval object
 */
void get_nextval(String T, int *nextval)
{
    int i = 1, j = 0; // i表示下标，初始化为0；j表示nextval数组的值，初始化为-1
    nextval[1] = 0;
    while (i < T[0])
    {

        if (j == 0 || T[i] == T[j])
        {
            i++;
            j++;
            if (T[i] != T[j])
            { //不同，该位置的nextval的值就是该位置的next值
                nextval[i] = j;
            }
            else
            { //相同，该位置的nextval的值就是该位置next值对应元素的nextval的值
                nextval[i] = nextval[j];
            }
        }
        else
        {
            j = nextval[j];
        }
    }
}

int Index_KMP1(String S, String T, int pos)
{
    int next[T[0]];
	get_nextval(T, next);

	int j = 1; //前缀指针
    int i = pos;
	while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
	{
		if (j == 0 || S[i] == T[j]) /* 两字母相等则继续，与朴素算法增加了j=0判断 */
		{
			++i;
			++j;
		}
		else			 /* 指针后退重新开始匹配 */
			j = next[j]; /* j退回合适的位置，i值不变 */
	}
	if (j > T[0])
		return i - T[0];
    else
	    return 0;
}
